/**
 * 
 */
package qy.course.cse494.web;

import java.util.HashSet;
import java.util.Hashtable;
import java.util.Set;
import java.util.Vector;

import qy.course.cse494.ir.DocumentHits;
import qy.course.cse494.ir.DocumentIndex;
import qy.course.cse494.ir.DocumentQuery;
import qy.course.cse494.ir.DocumentSearch;
import qy.course.cse494.util.Pair;

/**
 * @author qyan
 *
 */
public class WebAHRanker
{
	WebLinksExtractor _web_links_extractor;
	
	DocumentHits _top_authority_hits;
	DocumentHits _top_hub_hits;
	
	int _top_k = 10; // top k results should be returned. 
	int _propagate_depth = 1;  
	int _max_iterator = 1000;
	float _converged_epislon = 0.001f; // epsilon

	Vector<Integer> _seed_list = null;	
	Hashtable<Integer, Pair<Float, Float>> _page_ah_list = new Hashtable<Integer, Pair<Float, Float>>();

	/**
	 * Default constructor
	 * @param _web_links_extractor
	 */
	public WebAHRanker(WebLinksExtractor _web_links_extractor)
	{
		super();
		this._web_links_extractor = _web_links_extractor;
	}
	
	
	/**
	 * The interface to search a query, which requires the support from outsides
	 * Note that, we could embed the process of generation of seed_list in the 
	 * class later. (!!!!)
	 * @param seed_list
	 * @return
	 */
	public void search(Vector<Integer> seed_list)
	{
		search(seed_list, _top_k, _propagate_depth);
	}
	
	/**
	 * The interface below has the same function as the above.
	 * @param seed_list
	 * @param top_k
	 * @return
	 */
	public void search(Vector<Integer> seed_list, int top_k)
	{
		search(seed_list, top_k, _propagate_depth);
	}
	
	/**
	 * The interface below has the same function as the above.
	 * @param seed_list
	 * @param top_k
	 * @param depth
	 * @return
	 */
	public void search(Vector<Integer> seed_list, int top_k, int depth)
	{
		///////////////////////////////////////////////////////
		// Initiate the variables supporting the search
		_top_k = top_k;
		_propagate_depth = depth;
		_seed_list = seed_list;
		//
		_page_ah_list.clear();
		_top_authority_hits = new DocumentHits(top_k);
		_top_hub_hits = new DocumentHits(top_k);
		
		//////////////////////////////////////////////////////
		//
		long startTime, stopTime, runTime;
		startTime = System.currentTimeMillis();
		
		///////////////////////////////////////////////////////
		// 1. Generate the base set
		generate_base_set();
		
		stopTime = System.currentTimeMillis();
		runTime = stopTime - startTime;
		System.out.println("Run time for the base set generation: " + runTime);
		System.out.println("Size of root and base is : " + _seed_list.size() + " and "+ _page_ah_list.size());
		
		// 2. Compute the primary eigen vectors based on AH algorithm cite{***}
		compute_primary_eigen_vectors();
		
		runTime = System.currentTimeMillis() - stopTime;
		System.out.println("Run time for the a/h computation : " + runTime);
		
		//System.out.println(_page_ah_list.toString());
	}
	
	public DocumentHits get_top_authority_hits()
	{
		return _top_authority_hits;
	}
	
	public DocumentHits get_top_hub_hits()
	{
		return _top_hub_hits;
	}
	
	/**
	 * Using power iteration to compute the authority/hub vectors
	 *
	 */
	protected void compute_primary_eigen_vectors()
	{
		int iteration_count = 0;
		float distance_from_previous_value = 0f;
		
		do{
			++iteration_count;
			
			// 0. buckup the current ah values
			Hashtable<Integer, Pair<Float, Float>> ah_list = new Hashtable<Integer, Pair<Float, Float>>();
			
			//System.out.println(_page_ah_list);
			// 1. update the authority values
			float a_square_sum = 0;
			for(Integer cur_page_id : _page_ah_list.keySet())
			{
				Pair<Float, Float> cur_ah_value = _page_ah_list.get(cur_page_id);
				
				try
				{
					ah_list.put(cur_page_id, cur_ah_value.clone());
				} catch(CloneNotSupportedException e)
				{
					e.printStackTrace();
				}
				
				float a_value = 0f;
				Vector<Integer> cited_node_list = _web_links_extractor.CitationsBy(cur_page_id);
				for(Integer cur_cited_id : cited_node_list)
				{
					if(_page_ah_list.containsKey(cur_cited_id))
					{
						a_value += _page_ah_list.get(cur_cited_id).second();
					}
				}
				cur_ah_value.o1 = a_value;
				a_square_sum += a_value*a_value;
			}
			
			// 2. update the hub values
			float b_square_sum = 0;
			for(Integer cur_page_id : _page_ah_list.keySet())
			{
				Pair<Float, Float> cur_ah_value = _page_ah_list.get(cur_page_id);
				
				float b_value = 0f;
				Vector<Integer> cited_node_list = _web_links_extractor.LinksTo(cur_page_id);
				for(Integer cur_cited_id : cited_node_list)
				{
					if(_page_ah_list.containsKey(cur_cited_id))
					{
						b_value += _page_ah_list.get(cur_cited_id).first();
					}
				}
				cur_ah_value.o2 = b_value;
				b_square_sum += b_value*b_value;
			}
			
			// 3. normalize the vectors
			// 4. calculate the distance from the previous authority value
			distance_from_previous_value = 0f;
			a_square_sum = (float) Math.sqrt(a_square_sum);
			b_square_sum = (float) Math.sqrt(b_square_sum);
			for(Integer cur_page_id : _page_ah_list.keySet())
			{
				Pair<Float, Float> cur_ah_value = _page_ah_list.get(cur_page_id);
				cur_ah_value.o1 /= a_square_sum;
				cur_ah_value.o2 /= b_square_sum;
				//
				_top_authority_hits.add_hit(cur_page_id, cur_ah_value.o1);
				_top_hub_hits.add_hit(cur_page_id, cur_ah_value.o2);
				//
				Pair<Float, Float> cur_ah_value2 = ah_list.get(cur_page_id);
				float distance = cur_ah_value.o1 - ah_list.get(cur_page_id).first();
				distance_from_previous_value += distance * distance;
			}
			
			distance_from_previous_value = (float) Math.sqrt(distance_from_previous_value);
			
		}while(distance_from_previous_value > _converged_epislon && iteration_count < _max_iterator);
		//
		System.out.println("Iterations:" + iteration_count);
		System.out.println("Distance  :" + distance_from_previous_value);
	}
	
	protected void generate_base_set()
	{
		Set<Integer> base_set = new HashSet<Integer>();
		base_set.addAll(_seed_list);
		//
		for(int i=0; i<_propagate_depth; ++i)
		{
			base_set = generate_base_set(base_set);
		}
		
		//
		for(Integer cur_page_id : base_set)
		{
			_page_ah_list.put(cur_page_id, new Pair<Float, Float>(1.0f, 1.0f));
		}
		//
	}
	
	protected Set<Integer> generate_base_set(final Set<Integer> seed_set)
	{
		Set<Integer> base_set = new HashSet<Integer>();
		base_set.addAll(seed_set);
		
		for(Integer cur_seed : seed_set)
		{
			// deal with the forwards links
			Vector<Integer> forward_links_list = _web_links_extractor.LinksTo(cur_seed);
			base_set.addAll(forward_links_list);
		
			// deal with the back links
			Vector<Integer> back_links_list = _web_links_extractor.CitationsBy(cur_seed);
			base_set.addAll(back_links_list);
		}
		return base_set;
	}
	
	public static void stat_root_set()
	{
		DocumentIndex di = new DocumentIndex("data/index4result3", true);
		DocumentSearch searcher = new DocumentSearch(di);
		WebLinksExtractor web_links_extractor = new WebLinksExtractor("data/Hashedlinks4");
		//
		String query_str = "Transcripts";
		int[] root_set_size_list = {5, 10, 15, 20};
		for(int i=0; i<root_set_size_list.length; ++i)
		{
			System.out.println("The query:" + query_str);
			DocumentQuery query = new DocumentQuery(query_str);
	    	DocumentHits hits = searcher.search(query, root_set_size_list[i]);
	    	Set<Integer> rel_results_doc_set = searcher.get_hits_doc_hashcode();
	    	Vector<Integer> seed_list = new Vector<Integer>();
	    	for(int j=0; j<hits.length(); ++j)
	    	{
	    		String file_name = di.get_doc_name(hits.get_doc_id_ranked_at(j));
	    		seed_list.add(file_name.hashCode());
	    	}	
	    	//
	    	
	    	WebAHRanker ahranker = new WebAHRanker(web_links_extractor);
			ahranker.search(seed_list);
			
			int rel_num = 0;
			DocumentHits a_hits = ahranker.get_top_authority_hits();
			
			for(int k=0; k<a_hits.length(); ++k)
			{
				if(rel_results_doc_set.contains(a_hits.get_doc_id_ranked_at(k)))
				{
					++rel_num;
				}
			}
			
			System.out.println("Precision of Authority: " + (float)rel_num/a_hits.length());
			
			rel_num = 0;
			DocumentHits h_hits = ahranker.get_top_hub_hits();
			for(int k=0; k<h_hits.length(); ++k)
			{
				if(rel_results_doc_set.contains(h_hits.get_doc_id_ranked_at(k)))
				{
					++rel_num;
				}
			}
			
			System.out.println("Precision of Hub: " + (float)rel_num/h_hits.length());
		}
	}
	
	public static void stat()
	{
		DocumentIndex di = new DocumentIndex("data/index4result3", true);
		DocumentSearch searcher = new DocumentSearch(di);
		String[] query_list = {"Campus Tour","Medical Care","Transcripts",
				"Admissions","Employee Benefits","Languages","Hayden Library",
				"Parking Decal","SRC"};
		WebLinksExtractor web_links_extractor = new WebLinksExtractor("data/Hashedlinks4");
		
		for(int i=0; i<query_list.length; ++i)
		{
			System.out.println("The query:" + query_list[i]);
			DocumentQuery query = new DocumentQuery(query_list[i]);
	    	DocumentHits hits = searcher.search(query, 10);
	    	Set<Integer> rel_results_doc_set = searcher.get_hits_doc_hashcode();
	    	Vector<Integer> seed_list = new Vector<Integer>();
	    	for(int j=0; j<hits.length(); ++j)
	    	{
	    		String file_name = di.get_doc_name(hits.get_doc_id_ranked_at(j));
	    		seed_list.add(file_name.hashCode());
	    	}	
	    	//
	    	
	    	WebAHRanker ahranker = new WebAHRanker(web_links_extractor);
			ahranker.search(seed_list);
			//
			int rel_num = 0;
			DocumentHits a_hits = ahranker.get_top_authority_hits();
			
			for(int k=0; k<a_hits.length(); ++k)
			{
				if(rel_results_doc_set.contains(a_hits.get_doc_id_ranked_at(k)))
				{
					++rel_num;
				}
			}
			
			System.out.println("Precision of Authority: " + (float)rel_num/a_hits.length());
			
			rel_num = 0;
			DocumentHits h_hits = ahranker.get_top_hub_hits();
			for(int k=0; k<h_hits.length(); ++k)
			{
				if(rel_results_doc_set.contains(h_hits.get_doc_id_ranked_at(k)))
				{
					++rel_num;
				}
			}
			
			System.out.println("Precision of Hub: " + (float)rel_num/h_hits.length());
		}
		
		
	}
	
	/**
	 * Main entry, to debug the class
	 * @param args
	 */
	public static void main(String[] args)
	{
		//
//		DocumentIndex di = new DocumentIndex("data/result3index");
//		DocumentSearch searcher = new DocumentSearch(di);
//		DocumentQuery query = new DocumentQuery("src");
//    	DocumentHits hits = searcher.search(query, 10);
//    	Vector<Integer> seed_list = new Vector<Integer>();
//    	for(int i=0; i<hits.length(); ++i)
//    	{
//    		String file_name = di.get_doc_name(hits.get_doc_id_ranked_at(i)).substring(8);
//    		seed_list.add(file_name.hashCode());
//    	}
    	//
		
		WebAHRanker.stat_root_set();
		
//		int[] seed_array = {715399340, -45308014, 550886567, 1752489221, 
//				630440612, -1931177400, -1218086427, 306522483, 1437783669, -938820455};
//		Vector<Integer> seed_list = new Vector<Integer>();
//		for(int i=0; i<seed_array.length; ++i)
//		{
//			seed_list.add(seed_array[i]);
//		}
//		
//    	WebLinksExtractor web_links_extractor = new WebLinksExtractor("data/Hashedlinks4");
//		WebAHRanker ahranker = new WebAHRanker(web_links_extractor);
//		ahranker.search(seed_list);
//		//
//		System.out.println(ahranker.get_top_authority_hits());
//		System.out.println(ahranker.get_top_hub_hits());
	}


	/**
	 * @return the _page_ah_list
	 */
	public Hashtable<Integer, Pair<Float, Float>> get_ah_list()
	{
		return _page_ah_list;
	}
}
